//给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 
//
// 
//
// 示例 1: 
//
// 输入: [1,2,0]
//输出: 3
// 
//
// 示例 2: 
//
// 输入: [3,4,-1,1]
//输出: 2
// 
//
// 示例 3: 
//
// 输入: [7,8,9,11,12]
//输出: 1
// 
//
// 
//
// 提示： 
//
// 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。 
// Related Topics 数组 
// 👍 896 👎 0

package com.leetcode.editor.cn;

import java.util.Arrays;

//Java：缺失的第一个正数
class P41FirstMissingPositive {
    public static void main(String[] args) {
        Solution solution = new P41FirstMissingPositive().new Solution();
        // TO TEST
//        int[] nums = {3, 4, -1, 1};
//        int[] nums = {1, 2, 0};
//        int[] nums = {7, 8, 9, 11, 12};
//        int[] nums = {1, 1};
//        int[] nums = {1, 100};
        int[] nums = {1, 2, 2, 1, 3, 1, 0, 4, 0};
        System.out.println(solution.firstMissingPositive(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int firstMissingPositive(int[] nums) {
            Arrays.sort(nums);
            int index = 0;
            int first = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) {
                    index = i;
                    first = nums[i];
                    break;
                }
            }
            if (first == 0 || first > 1) {
                return 1;
            }
            while (index < nums.length - 1) {
                if (nums[++index] - first <= 1) {
                    first = nums[index];
                } else {
                    return first + 1;
                }
            }
            return nums[nums.length - 1] + 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}